// 给定一个未排序的整数数组nums
// 要求返回最长递增子序列的个数

// 解题思路：动态规划
// 1. 定义状态：dp[i]，表示以第i个元素结尾的前i个元素中最长严格递增子序列的长度
// 2. 状态转义方程，两重循环前i个数字，对于0 <= j <= i
//      1. 当nums[j] < nums[i]时，nums[i]可以在nums[j]后面，此时以第i个数字结尾的最长严格递增子序列长度+1，
//         即dp[i] = dp[j] + 1
//      2. 当nums[j] >= nums[i],可以直接跳过
//   状态转移方程即为：dp[i] = Math.max(dp[i], dp[j]+1), 0 <= j <= i, nums[j] < nums[i]
// 3. 求解最长递增子序列的个数，则在求解过程中维护一个count数组，用来保存以nums[i]结尾的最长递增子序列的个数
//    对于0 <= j <= i
//      1. 当nums[j] < nums[i],且dp[j] + 1 > dp[i],说明第一次找到dp[j]+1长度且以nums[i]结尾的最长递增子序列，则
//          以nums[i]结尾的最长递增子序列的组合数就等于一nums[j]结尾的组合数，即count[i] = count[j]
//      2. 当nums[j] < nums[i],且dp[j] + 1 = dp[i],说明以nums[i]结尾且长度为dp[j] + 1的递增序列已经找到过一次了，则
//          以nums[i]结尾的最长递增子序列的组合数要加上以nums[j]结尾的组合数，即count[i] += count[j]
//      3. 然后根据遍历dp数组得到的最长递增子序列的长度max_l·ength,然后再一次遍历dp数组，将所有dp[i] === max_length情况
//          下的组合数count[i]累加起来，即为最长递增序列的个数
function findNumberOfLIS(nums) {
    let dp = new Array(nums.length).fill(1)
    let count = new Array(nums.length).fill(1)
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    // 更新dp[i]
                    dp[i] = dp[j] + 1
                    count[i] = count[j]
                } else if (dp[j] + 1 === dp[i]) {
                    count[i] += count[j]
                }
            }            
        }        
    }
    let maxLen = Math.max(...dp)
    let res = 0
    for (let i = 0; i < count.length; i++) {
        if (dp[i] === maxLen) {
            res += count[i]
        }        
    }
    return res
}

let nums = [1, 3, 5, 4, 7]
console.log(findNumberOfLIS(nums));